2023 巅峰极客-Rosita

Van1sh 比赛小屋 Write Up

创建时间:2023-07-24 01:00

字数:2.4k 阅读:

由于莫得学生身份了，所以上周五巅峰极客只报了个野队看了一下题，然后一下午就过去了。 HSSP 类的问题之前没怎么接触，再加上对垂直格这块的东西还没有琢磨透，所以比赛的时候没有把题给做出来，赛后也花了好长时间去理解，还是太菜了。

题目代码

# Problem by rec, without any sleep at all.
from Crypto.Util.number import bytes_to_long as b2l
from hashlib import sha256
from os import urandom
from secret import p, a, b, flag

ECC = EllipticCurve(GF(p), [a, b])
R, E, C = [ECC.random_point() for _ in range(3)]

pad = lambda m: urandom(8) + m + b'\x00' * (ZZ(p).nbits() // 8 - len(m) - 8 - 1)
out = list()
for i in range(len(flag)):
    m = pad(chr(flag[i]).encode())
    nonce = urandom(16)
    sh = sha256(nonce + m).digest()
    
    Q = b2l(m)*R + b2l(nonce)*E + b2l(sh)*C
    out.append(Q.xy())

with open('out.tuo', 'w') as f:
    f.write(str(out))

代码不难理解，题目基于椭圆曲线，但是没有给出曲线的参数。然后将 flag 逐字节进行一个操作：

首先对 flag 的一个字节进行填充得到 m ：八字节随机字符串||flag 的字节|| \x00，总共长度为 63
虽然生成 16 字节随机字符串 nonce
计算 nonce || m 的哈希 sh
输出 $Q = m\times R+nonce \times E+sh\times C$，其中 $R,E,C$ 为未知随机点。

我们手里仅有这一系列的 $Q$ 点。所以第一步肯定是要先恢复曲线的信息。

我们知道曲线的表达式为 $y^2 \equiv x^3 +ax+b \pmod p \to y^2 = x^3 +ax+b +kp$

于是有 $y^2-x^3 = ax+b+kp$

考虑消元，于是找两个点做减法（不是曲线上的点减法，是我们这里的等式相减）：

$Q_1-Q_2$ ：$(y_1^2-x_1^3) - (y_2^2-x_2^3) = a(x_1-x_2) + (k_1-k_2)p$

$Q_1-Q_3$：$(y_1^2-x_1^3) - (y_3^2-x_3^3) = a(x_1-x_3) + (k_1-k_3)p$

还想把 $a$ 项给消了，于是：

$(x_1-x_3)(Q_1-Q_2) - (x_1-x_2)(Q_1-Q_3)$

$= (x_1-x_3)(y_1^2-x_1^3) - (y_2^2-x_2^3)-(x_1-x_2)(y_1^2-x_1^3) - (y_3^2-x_3^3)$

$=(x_1-x_3)(k_1-k_2)p-(x_1-x_2)(k_1-k_3)p$

我们得到一个 $Kp$，即 $p$ 的一个倍数。

于是我们再用一点 $Q_4$ 就能得到 $p$ 的另一个倍数，然后求他们的公因子，再去除一些小因子，就能得到素数，也就是模数 $p$ 了。

有了模数 $p$，我们就能计算

$a \equiv \frac{(y_1^2-x_1^3) - (y_2^2-x_2^3) }{x_1-x_2} \pmod p$

$b \equiv y^2-x^3 - ax \pmod p $

从而恢复曲线的所有参数了。

from Crypto.Util.number import GCD,isPrime
def recover_para(Q):
	x1,y1 = Q[0]
	x2,y2 = Q[1]
	x3,y3 = Q[2]
	x4,y4 = Q[3]
	t12_13 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x3)
	t13_12 = ((y1**2 - x1**3)-(y3**2 - x3**3)) * (x1-x2)
	k1p = t12_13-t13_12

	t12_14 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x4)
	t14_12 = ((y1**2 - x1**3)-(y4**2 - x4**3)) * (x1-x2)
	k2p = t12_14-t14_12

	p = factor(GCD(k1p,k2p))[-1][0]
	assert isPrime(int(p))

	a = ((y1^2-x1^3)-(y2^2-x2^3))/(x1-x2) % p
	b = (y1^2-x1^3-a*x1) % p

	E = EllipticCurve(GF(p),[a,b])

	assert E(Q[0])
	return E,(a,b,p)


Q = [(),(),()....]
E,_ = recover_para(Q)

之后发现，这条曲线的 order 和 p 相等，因此利用 smart attack，我们能解决这条曲线上的 DLP 。

那么回到问题 $$Q = m\times R+nonce \times E+sh\times C$$，由于不知道 $R,E,C$，方便起见我们直接再生成一个点 $G$，分别设 $R = rG,E=eG,C=cG$，那么就有 $$Q = (mr+nonce\cdot e +sh \cdot c)\times G$$

然后我们利用 smart attack 解 DLP：

def HenselLift(P,p,prec):
	E = P.curve()
	Eq = E.change_ring(QQ)
	Ep = Eq.change_ring(Qp(p,prec))
	x_P,y_P = P.xy()
	x_lift = ZZ(x_P)
	y_lift = ZZ(y_P)
	x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')
	f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6
	g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)
	gDiff = g.diff() # differential 
	for i in range(1,prec):
		uInv = ZZ(gDiff(y=y_lift))
		u = uInv.inverse_mod(p^i)
		y_lift = y_lift - u*g(y_lift)
		y_lift = ZZ(Mod(y_lift,p^(i+1)))
	y_lift = y_lift+O(p^prec)
	return Ep([x_lift,y_lift])


def SmartAttack(P,Q,p,prec):
	E = P.curve()
	Eqq = E.change_ring(QQ)
	Eqp = Eqq.change_ring(Qp(p,prec))

	P_Qp = HenselLift(P,p,prec)
	Q_Qp = HenselLift(Q,p,prec)

	p_times_P = p*P_Qp
	p_times_Q = p*Q_Qp

	x_P,y_P = p_times_P.xy()
	x_Q,y_Q = p_times_Q.xy()

	phi_P = -(x_P/y_P)
	phi_Q = -(x_Q/y_Q)
	k = phi_Q/phi_P
	k = Mod(k,p)
	return k

G = ECC.random_point()
Points = []
for each in Q:
    Points.append(E(each))
h = []
for P in Points:
	h.append(SmartAttack(G,P,p,8))

我们获得了一系列值：$m_ir+nonce_i\cdot e +sh_i \cdot c$，

其中 $m_i$ 是八个字节随机字符串+flag的一个字节+54个 ‘’\x00’’，$nonce_i$ 是16字节随机字符串，$sh_i$ 可以看作 32 字节随机字符串。

由于 $m_i$ 后面全是 “\x00”，所以有 bytes_to_long(mi) = bytes_to_long(mi[:9]) * 256^54，我们把这个 $256^{54}$ 算到 $r$ 身上的话，$m_i$ 也就可以看作是九个字节的随机字符串。于是我们注意到，这个式子中的三项都是由一个不变的很大的数 $r,e,c$ 和变化的但是很小的数 $m_i,nonce_i,sh_i$ 组成的。相较于经典的 HSSP 问题

这里的系数不是 ${0,1}$，但是也不是很大，也有称之为 The Hidden Lattice Problem（HLP），解决这一类问题使用的手法一般是构造垂直格：对由 $h$ 组成的向量 $\overrightarrow{h}$ 进行两次正交以找到组成 $h$ 中的较短的那一部分。

首先我们构造向量 $\overrightarrow{h}$ 的垂直格（也即找到 $\overrightarrow{h}$ 的解空间），格中每条向量 $l$ 均满足 $l \cdot \overrightarrow{h} = 0$

格的样式为

$H =
\begin{bmatrix}
k\cdot h_0 &1 & & & & & \newline
k\cdot h_1 & &1 & & & & \newline
k\cdot h_2 & & & \ddots & & & \newline
\vdots & & & &1 & & \newline
k\cdot h_{n-1} & & &\dots & &1 & \newline
k\cdot p & & &\dots & & &1 \newline
\end{bmatrix}$，其中 $k$ 是一个较大的常数，例如 $2^{1024}$，$p$ 是模数

k = 2^1024

h_v = matrix(ZZ,[h+[p]]).T
h_v = h_v*k
Q = diagonal_matrix([1]*len(h_v.columns()[0]))

m = block_matrix(ZZ,[[h_v,Q]])
L = m.LLL()	#  the orthoginal lattice of h

l = []
for each in L[:-1]:
    assert each[0] == 0
    l.append(list(each)[1:])

然后使用 LLL 进行规约。由于我们的 $\overrightarrow{h}$ 是 $n\times 1$ 的，因此解空间的秩应该是 $n-1$，所以我们可以拿到一个 $n-1 \times n$ 的格 $L=\overrightarrow{h}^{\bot}$。

于是我们有 $l \cdot \overrightarrow {h} = l \cdot \overrightarrow{m \cdot r}+l \cdot \overrightarrow{nonce\cdot e} +l \cdot \overrightarrow{sh \cdot c} + l \cdot \overrightarrow{kp}) = 0$

考虑到如果 $l\cdot \overrightarrow{m} = 0,l\cdot \overrightarrow{nonce} =0,l\cdot \overrightarrow{sh}=0,l \cdot \overrightarrow{k}=0$ 也能使得上式成立，而且 $\overrightarrow{m}$ 等向量还比较短，于是我们求一个 $L$ 的垂直格 $L^{\bot}$ （这一块其实不是很理解，虽然该条件能使得上式成立，但并不能说上式成立会保证满足该条件，属于是充分不必要条件，不过经过实践后发现确实存在该条件）

由于我们的 $\overrightarrow{h}$ 是由四项组成的，于是我们用 $(n-1-3) \times n$ 的矩阵（这样子解空间的秩为 $4$）

$O =
\begin{bmatrix}L^\top & 1\end{bmatrix}$

然后使用 LLL 进行规约。在第一行我们能够得到的最短的向量，应该就是由八个随机字节和一个 flag 字节组成的 $\overrightarrow {m}$ ，然后我们取最低字节，就能获取到 flag 了。

ll = (matrix(ZZ,l[:-3]).T)*k
mm = block_matrix(ZZ,[[ll,1]])
LL = mm.LLL()

assert sum(LL[0][:70]) == 0

print("".join(chr(i & 0xff) for i in LL[0][70:]))

# Congratulations! Your flag is: flag{893d041e-c0a2-3145-5320-cdee7d3c87fb}

最后整合一下

from Crypto.Util.number import GCD,isPrime

def recover_para(Q):
	x1,y1 = Q[0]
	x2,y2 = Q[1]
	x3,y3 = Q[2]
	x4,y4 = Q[3]
	t12_13 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x3)
	t13_12 = ((y1**2 - x1**3)-(y3**2 - x3**3)) * (x1-x2)
	k1p = t12_13-t13_12

	t12_14 = ((y1**2 - x1**3)-(y2**2 - x2**3)) * (x1-x4)
	t14_12 = ((y1**2 - x1**3)-(y4**2 - x4**3)) * (x1-x2)
	k2p = t12_14-t14_12

	p = factor(GCD(k1p,k2p))[-1][0]
	assert isPrime(int(p))

	a = ((y1^2-x1^3)-(y2^2-x2^3))/(x1-x2) % p
	b = (y1^2-x1^3-a*x1) % p

	E = EllipticCurve(GF(p),[a,b])

	assert E(Q[0])

	return E,(a,b,p)



def HenselLift(P,p,prec):
	E = P.curve()
	Eq = E.change_ring(QQ)
	Ep = Eq.change_ring(Qp(p,prec))
	x_P,y_P = P.xy()
	x_lift = ZZ(x_P)
	y_lift = ZZ(y_P)
	x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')
	f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6
	g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)
	gDiff = g.diff() # differential 
	for i in range(1,prec):
		uInv = ZZ(gDiff(y=y_lift))
		u = uInv.inverse_mod(p^i)
		y_lift = y_lift - u*g(y_lift)
		y_lift = ZZ(Mod(y_lift,p^(i+1)))
	y_lift = y_lift+O(p^prec)
	return Ep([x_lift,y_lift])


def SmartAttack(P,Q,p,prec):
	E = P.curve()
	Eqq = E.change_ring(QQ)
	Eqp = Eqq.change_ring(Qp(p,prec))

	P_Qp = HenselLift(P,p,prec)
	Q_Qp = HenselLift(Q,p,prec)

	p_times_P = p*P_Qp
	p_times_Q = p*Q_Qp

	x_P,y_P = p_times_P.xy()
	x_Q,y_Q = p_times_Q.xy()

	phi_P = -(x_P/y_P)
	phi_Q = -(x_Q/y_Q)
	k = phi_Q/phi_P
	k = Mod(k,p)
	return k


# L: the orthoginal lattice of h
def orthoginal_of_vector_modp(h,p):
	k = 2^1024

	h_v = matrix(ZZ,[h+[p]]).T
	h_v = h_v*k
	Q = diagonal_matrix([1]*len(h_v.columns()[0]))

	m = block_matrix(ZZ,[[h_v,Q]])
	L = m.LLL()	#  the orthoginal lattice of h
	l = []
	for each in L[:-1]:
	    assert each[0] == 0
	    l.append(list(each)[1:])
	return l

def orthoginal_of_lattce(L):
	mm = block_matrix(ZZ,[[L,1]])
	LL = mm.LLL()
	return LL



Q = [(),(),()]
E,(a,b,p) = recover_para(Q)

G = E.random_point()
Points = []
for each in Q:
    Points.append(E(each))

h = []
for P in Points:
	h.append(SmartAttack(G,P,p,8))
	print(len(h))

l = orthoginal_of_vector_modp(h,p)
ll = (matrix(ZZ,l[:len(l[0])-4]).T)*k
LL = orthoginal_of_lattce(ll)

assert sum(LL[0][:len(l[0])-4]) == 0

print("".join(chr(i & 0xff) for i in LL[0][len(l[0])-4:]))

（感觉自己现在所掌握的知识点有点杂乱了，后续想把这些搞成一个体系，比如整数分解问题搞一起，离散对数问题搞一起，SVP 搞一起，LWE 搞一起之类的。。。先立个 flag再说）

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com